package org.hhchat.leetcode.dp;

/**
 * Created this one by HMH on 2017/6/11.
 */
public class code464 {

    public static class Solution {
        public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
            if(desiredTotal<=1){
                return true;
            }
            if ((1 + maxChoosableInteger) * maxChoosableInteger / 2 < desiredTotal) {
                return false;
            }
            //生成mark
            Boolean dp[] = new Boolean[1 << maxChoosableInteger];
            return canWin(maxChoosableInteger, desiredTotal,0, dp);
            //开始递归
        }

        public boolean canWin(int maxChoosableInteger,int desiredTotal, int mark,Boolean dp[]){
            if(dp[mark]!=null){
                return dp[mark];
            }
            for(int i=maxChoosableInteger ;i>=1 ;i--){
                //这次要选择的数字
                int bit = 1<<(i-1);
                //如果没有被选中
                if((mark & bit) ==0){
                    if(i>=desiredTotal){
                        dp[mark] = true;
                        return dp[mark];
                    }
                    mark ^= bit;
                    boolean opWin = canWin(maxChoosableInteger,desiredTotal-i,mark,dp);
                    mark^=bit;
                    if(!opWin){
                        dp[mark]=true;
                        return dp[mark];
                    }
                }
            }
            //都试了不行
            dp[mark]=false;
            return false;
        }
    }

    public static void main(String[] args){

    }

}
